package 纯数组;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class No229求众数II {

    /**
     * 给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
     * 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
     *
     * 示例 1：
     * 输入：[3,2,3]
     * 输出：[3]
     * 示例 2：
     * 输入：nums = [1]
     * 输出：[1]
     * 示例 3：
     * 输入：[1,1,1,3,3,2,2,2]
     * 输出：[1,2]
     *  
     * 提示：
     * 1 <= nums.length <= 5 * 104
     * -109 <= nums[i] <= 109
     */

    public List<Integer> majorityElement(int[] nums) {

        /**
         * 单候选人的摩尔投票法可判断超过一半的最多的元素;
         * 双候选人的摩尔投票法只能判断最多的两个元素;
         * 三只能判断最多的三个元素;
         * 既然是超过 [1/3] 说明,最多两个元素能超过[1/3],不可能有三个元素
         */

        List<Integer> result=new ArrayList<>();

        if(nums.length<1){
            return result;
        }
        if(nums.length<2){
            result.add(nums[0]);
            return result;
        }

        //我直接0就行
        int num1=0;
        int num2=0;
        int count1=0;
        int count2=0;

        for (int i = 0; i < nums.length; i++) {

            if(nums[i]==num1){
                count1++;
                continue;
            }
            if(nums[i]==num2){
                count2++;
                continue;
            }

            if(count1==0){
                num1=nums[i];
                count1=1;
                continue;
            }

            if(count2==0){
                num2=nums[i];
                count2=1;
                continue;
            }

            count1--;
            count2--;

        }

        count1=0;
        count2=0;

        for (int num : nums) {
            if(num==num1){
                count1++;
            }else if(num==num2){
                //使用else if 防止相同的数字发生
                count2++;
            }
        }

        if(count1>(nums.length/3)){
            result.add(num1);
        }
        if(count2>(nums.length/3)){
            result.add(num2);
        }

        return result;

    }

    public static void main(String[] args) {
        No229求众数II n=new No229求众数II();
        int[] arr={0,0,0,0,0,1,1,1,1,1,2};
        List<Integer> result = n.majorityElement(arr);
        System.out.println(JSON.toJSONString(result));
    }

}
